package com.yanyuan.algorithm.list;

/**
 * @Description 单链表类
 * @Author yanyuan
 * @Date 21:46 2020/5/10
 * @Version 1.0
 **/
public class SingleLinkedList {
    //1.节点的个数
    private int size;
    //2. 头节点
    private Node head;


    public class Node{
        private Object data;//内部类元素，OBJECT类型
        private Node next;

        public Node() {
        }

        public Node(Object data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * @param object 添加的元素
     * @return
     */
    public Object addNode(Object object){
        Node newHead = new Node(object);//每次添加的元素为头节点
        if(size == 0){
            head = newHead;
        }else {
            newHead.next = head;
            head = newHead;
        }
        size++;
        return object;
    }

    /**
     * 判读是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    public void display(){
        if(isEmpty()){
            System.out.println("单向链表为空");
            return;
        }
        Node node = head;
        int tempSize = size; //临时长度
        System.out.print("[");
        while (tempSize > 0){
            System.out.print(node.data);
            if(node.next != null) {
                System.out.print(" -> ");
            }
            node = node.next;//当前节点指向下一个节点，继续循环
            tempSize--;
        }
        System.out.print("] \n");
    }

    /**
     * 删除头节点
     * @return
     */
    public Node deleteHead(){
        Node delNode = head;
        head = head.next;
        size--;
        return delNode;
    }

    public boolean delete(Object object){
        if(isEmpty()) return false;

        Node current = head; //指定当前节点为头节点
        Node previous = head;//指定前驱节点为头节点

        //判断条件，如果当前节点数据不等于需要删除的数据，则继续
        while (current.data != object){
            if(current.next == null) return false;
            previous = current;
            current = current.next;
        }
        //删除节点是否为头节点
        if(current == head){
            head = head.next;
        }else {
            //当前节点的前驱节点指定当前节点的下一个节点，当前节点没有任何对象引用。
            previous.next = current.next;
        }
        size--;
        return true;
    }

    public Node find(Object object){
        Node current = head;
        int tempSize = size; //临时变量，用于循环
        while (tempSize > 0){
            if(current.data.equals(object)){
                return current;
            }else {
                current = current.next;
                tempSize--;
            }
        }
        return null;

    }

    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.addNode("郭嘉");
        list.addNode("司马懿");
        list.addNode("荀彧");
        list.display();

        System.out.println("查询数据为【司马懿】的节点：" + list.find("司马懿"));

        System.out.println("删除头节点：" + list.deleteHead());
        list.display();

        list.addNode("许攸");
        list.addNode("贾诩");
        list.display();

        System.out.println("删除数据为郭嘉的节点：" + list.delete("郭嘉"));
        list.display();



    }
}
